#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 590. N 叉树的后序遍历.py
@time: 2022/2/21 15:54
@desc: https://leetcode-cn.com/problems/n-ary-tree-postorder-traversal/
> 给定一个 n叉树的根节点root，返回 其节点值的 后序遍历 。
n 叉树 在输入中按层序遍历进行序列化表示，每组子节点由空值 null 分隔（请参见示例）。

1. Ot(N), Os(N)
'''
# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children

# 递归
class Solution(object):
    def postorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        """
        if not root: return []
        res = []
        def traversal(root):
            if not root: return
            for node in root.children: traversal(node)
            res.append(root.val)
        traversal(root)
        return res


"""
# Definition for a Node.
class Node(object):
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children
"""


# 迭代
class Solution(object):
    def postorder(self, root):
        """
        :type root: Node
        :rtype: List[int]
        思路：根右左遍历，然后逆过来
        """
        if not root: return []
        stack, res = [root], []
        while stack:
            node = stack.pop()
            res.append(node.val)
            for child in node.children:
                # 从左到右入栈，这样子可以从右到左弹出
                stack.append(child)

        return res[::-1]
